package middle;

import sword.offer.common.GenerateTree;
import sword.offer.common.TreeNode;

import java.util.*;

/**
 * 给定一棵二叉树 root，返回所有重复的子树。
 *
 * 对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
 *
 * 如果两棵树具有相同的结构和相同的结点值，则它们是重复的。
 *
 * 链接：https://leetcode.cn/problems/find-duplicate-subtrees
 * @author 胡宇轩
 * @Email: programboy@163.com
 */
public class FindDuplicateSubtrees {
    public static void main(String[] args) {
        TreeNode node = GenerateTree.generateTree1(Arrays.asList(1, 2, 3, 4, null, 2, 4, null, null, 4));
        Solution solution = new Solution();
        solution.findDuplicateSubtrees(node);
    }

    static class Solution {
        Map<String, Integer> count = new HashMap<>();
        List<TreeNode> result = new ArrayList<>();
        public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
            recur(root);
            return result;
        }

        private String recur(TreeNode root) {
            if(root == null) {
                return "#";
            }
            String serial = root.val + "," + recur(root.left) + recur(root.right);
            count.put(serial, count.getOrDefault(serial, 0) + 1);
            if (count.get(serial) == 2) {
                result.add(root);
            }
            return serial;
        }
    }
}
